package com.fengye.algorithms.leecode.dp;

/**
 * @Author fengye
 * @Date 2023/4/8 11:17
 **/
public class StrInterleave97 {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length();
        int m = s2.length();
        int t = s3.length();

        if(n+m != t) {
            return false;
        }

        boolean[][] flag = new boolean[n + 1][m + 1];

        flag[0][0] = true;
        for(int i=0;i<=n;i++) {
            for(int j=0;j<=m;j++) {
                int p = i+j-1;
                if(i>0) {
                    // 如果前一个字符已经于s3相等，那么加上当前字符于s3相等，则符合条件，标记true
                    flag[i][j] = flag[i][j] || (flag[i-1][j] && s1.charAt(i-1) == s3.charAt(p));
                }
                if(j>0) {
                    flag[i][j] = flag[i][j] || (flag[i][j-1] && s2.charAt(j-1) == s3.charAt(p));
                }
            }
        }

        return flag[n][m];
    }
}
